from BinaryTree import *

class Solution:
	# @param root, a tree node
	# @return a boolean
	def isValidBST(self, root):
		if root is None:
			return True
		left = root.left
		right = root.right
		if left and left.val >= root.val:
			return False
		if right and right.val <= root.val:
			return False
		return bool(self.check_left(root.left, root.val) and self.check_right(root.right, root.val))

	def check_left(self, root, maxi):
		if root is None:
			return True
		left = root.left
		right = root.right
		if root.val >= maxi:
			return False
		if left and left.val >= root.val:
			return False
		if right and right.val <= root.val:
			return False
		while right:
			if right.val >= maxi:
				return False
			right = right.right
		return bool(self.check_left(root.left, root.val) and self.check_right(root.right, root.val))

	def check_right(self, root, mini):
		if root is None:
			return True
		left = root.left
		right = root.right
		if root.val <= mini:
			return False
		if left and left.val >= root.val:
			return False
		if right and right.val <= root.val:
			return False
		while left:
			if left.val <= mini:
				return False
			left = left.left
		return bool(self.check_left(root.left, root.val) and self.check_right(root.right, root.val))


if __name__ == '__main__':
	tree = BinaryTree([2, 1, 6, "#", 3, 4, "#"])
	tree.display()
	root = tree.tree()
	so = Solution()
	print so.isValidBST(root)